package com.c2b.algorithm.newcoder.hash;

/**
 * <a href="https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">缺失的第一个正整数</a>
 * <p>
 * 给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数<br>
 * 进阶： 空间复杂度O(1)，时间复杂度O(n)
 * </p>
 * <p>
 * 数据范围:−2^31≤nums[i]≤2^31−1，0≤len(nums)≤5∗10^5
 * </p>
 * <pre>
 *     示例1： [1,0,2]         =>3
 *     示例2： [-2,3,4,1,5]    =>2
 *     示例3： [4,5,6,8,9]     =>1
 * </pre>
 *
 * @author c2b
 * @since 2023/3/14 17:14
 */
public class BM0053MinNumberDisappeared_M {

    /**
     * 原地哈希
     */
    public int minNumberDisappeared(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 1;
        }
        int length = nums.length;
        // 可能出现负数，将所有的负数置为len长度+1.用于区别
        for (int i = 0; i < length; i++) {
            if (nums[i] < 0) {
                nums[i] = length + 1;
            }
        }
        for (int i = 0; i < length; i++) {
            if (Math.abs(nums[i] - 1) <= length) {
                nums[nums[i] - 1] = -1 * Math.abs(nums[Math.abs(Math.abs(nums[i] - 1)) - 1]);
            }

        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0 && nums[i] < length) {
                return i + 1;
            }
        }
        return length + 1;
    }

    public static void main(String[] args) {
        BM0053MinNumberDisappeared_M bm0053MinNumberDisappeared_m = new BM0053MinNumberDisappeared_M();
        System.out.println(bm0053MinNumberDisappeared_m.minNumberDisappeared(new int[]{1, 0, 2}));
    }
}
